﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ArrayCode.DoublePointer27
{
    //双指针法（快慢指针法）
    //通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
    //在数组和链表的操作中非常常见。
    class DoublePointer27
    {
        // ================================= 力扣27 移除元素
        //给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于 val的元素，并返回移除后数组的新长度。
        //不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
        //元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
        public int RemoveElement(int[] nums, int val)
        {//方法一
            int left = 0;
            for (int right = 0; right < nums.Length; right++)
            {
                if (nums[right] != val)
                {   //删除元素，所以输出数组长度一定小于等于数组长度
                    //可以将输出的数组直接写在输入数组上。
                    nums[left] = nums[right];
                    left++;
                }
            }
            return left;
        }
        public int RemoveElement_2(int[] nums, int val)
        {//方法二
            //会改变原数组元素顺序
            //避免了需要保留的元素重复赋值操作
            //最坏的情况下合起来只遍历数组一次
            int left = 0, right = nums.Length;
            while (left < right)
            {
                if(nums[left] == val)
                {
                    nums[left] = nums[right];
                    right--;
                }
                else
                {
                    left++;
                }
            }
            return left;
        }

        //========================== 力扣26 删除有序数组中的重复项
        //给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
        //不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
        public int RemoveDuplicates(int[] nums)
        {
            if (nums.Length == 0)
                return 0;

            int j = 1;
            for(int i = 1;i<nums.Length;i++)
            {
                if(nums[i] != nums[i-1])
                {//有序数组有重复的话 必然是挨在一起的。
                    nums[j] = nums[i];
                    j++;
                }
            }
            return j;
        }

        //=========================== 力扣283 移动零
        //给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序
        public void MoveZeroes(int[] nums)
        {
            int i = 0, j = 0, len = nums.Length;
            for(j = 0;j<len;j++)
            {
                if (nums[j] != 0)
                {
                    int tem = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tem;
                    i++;
                }
            }
        }

        //============================ 力扣844 比较含退格的字符串
        //给定S和T两个字符串，当他们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。#代表退格字符
        //如果对空文本输入退格字符，文本继续为空

        //方法一 重构字符串
        //时间复杂度O(m+n),m和n分别为字符串s和t的长度，我们需要各遍历一次
        //空间复杂度O(m+n),主要为还原出的字符串的开销
        public bool BackspaceCompare(string s, string t)
        {
            s = getString(s);
            t = getString(t);
            return s == t;
        }
        private string getString(string str)
        {//处理字符串，遇到#就删掉
            string tem = "";
            char[] chars = str.ToCharArray();
            for(int i = 0;i<chars.Length;i++)
            {
                if (chars[i] == '#')
                {
                    if (tem.Length > 0)
                        tem = tem.Remove(tem.Length - 1);
                }
                else
                    tem += chars[i];
            }
            return tem;
        }
        //方法二 双指针法
        //一个字符是否被删掉，取决于改字符后面的退格符，因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉
        //时间复杂度：O(n+m)
        //空间复杂度：O(1)，对于每个字符串，我们只需要定义一个指针和一个计数器即可
        public bool BackspaceCompare_2(string s, string t)
        {
            int i = s.Length - 1, j = t.Length - 1;
            int skipS = 0, skipT = 0;//我们定义 skip 表示当前待删除的字符的数量
            
            
            while (i >= 0 || j >= 0)
            {
                while(i >= 0)
                {
                    if (s[i] == '#')//若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 11
                    {
                        skipS++;
                        i--;
                    }
                    else if (skipS > 0)//若该字符为普通字符：若skip 不为 00，则说明当前字符需要删去，我们让 skip 减 11
                    {
                        skipS--;
                        i--;
                    }
                    else//若 skip 为 00，则说明当前字符不需要删去；
                        break;
                }
                while(j >= 0)
                {
                    if (t[j] == '#')
                    {
                        skipT++;
                        j--;
                    }
                    else if (skipT > 0)
                    {
                        skipT--;
                        j--;
                    }
                    else
                        break;
                }
                if(i>=0 && j>=0)
                {
                    if (s[i] != t[j])
                        return false;
                }
                else
                {
                    if (i >= 0 || j >= 0)
                        return false;
                }
                i--;
                j--;
            }
            return true;
        }

        //=================================== 力扣977 有序数组的平方
        //给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
        //使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况
        public int[] SortEdSquares(int[] nums)
        {
            int[] result = new int[nums.Length];
            int i = 0, j = result.Length - 1, k = result.Length - 1;
            while(k >= 0)
            {
                if(nums[i] * nums[i] < nums[j] * nums[j])
                {
                    result[k] = nums[j] * nums[j];
                    j--;
                }
                else
                {
                    result[k] = nums[i] * nums[i];
                    i++;
                }
                k--;
            }
            return result;
        }
    }
}
